A semiconductor integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, wires, etc., that are fabricated by forming layers of different materials and of different geometric shapes on various regions of a silicon wafer. The design of an integrated circuit transforms a circuit description into a geometric description called a layout. The process of converting specifications of an integrated circuit into a layout is called the physical design.
After the layout is complete, it is then checked to ensure that it meets the design requirements. The result is a set of design files, which are then converted into pattern generator files. The pattern generator files are used to produced patterns called masks by an optical or electron beam pattern generator. Subsequently, during fabrication of the IC, these masks are used to pattern chips on the silicon wafer using a sequence of photolithographic steps. Electronic components of the IC are therefore formed on the wafer in accordance with the patterns.
Many phases of physical design may be performed with computer aided design (CAD) tools or electronic design automation (EDA) systems. To design an integrated circuit, a designer first creates high level behavior descriptions of the IC device using a high-level hardware design language. An EDA system typically receives the high level behavior descriptions of the IC device and translates this high-level design language into netlists of various levels of abstraction using a computer synthesis process. A netlist describes interconnections of nodes and components on the chip and includes information of circuit primitives such as transistors and diodes, their sizes and interconnections, for example.
Geometric information about the placement of the nodes and components onto the chip is determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip and the routing process is the process for creating interconnections between the blocks and components according to the specified netlist.
Many routing programs use “grid-based” routing techniques. During grid-based routing, wires are routed along defined and equally spaced grid lines of a grid array. Grid lines of the grid array are used in the routing process to speed up the process of finding the wire routing solutions by reducing the number of pathways to consider for routing. The grid-based router, however, has several drawbacks.
A disadvantage of the grid-based router is that it is difficult for a grid-based router to route with circuit blocks that do not have a signal-defined grid array. Modern IC and circuit board designs typically include circuit blocks having different dimension grid arrays. As a result, the grid-based router may not be able to match pins of different blocks with different dimension grid arrays. Another disadvantage of the grid-based router is that it is very inflexible, because it is highly dependent on wire length, wire width, and wire separation, and not on a predefined wire grid array. Therefore, for example, forcing wires to lie on predefined grid lines may not optimally address the greater underlying problem of signal delay. Another problem of the grid-based router is that it tends to waste a large percentage of routable area within an integrated circuit substrate.
Gridless routers can also be employed to route an integrated circuit design. A shape-based router is an example of a gridless router. Because the gridless router is not directly tied to a predefined grid array, it alleviates some of the grid-based router's disadvantages. The shape-based router, however, has its own problems. For example, known approaches to implementing this type of gridless router use a non-hierarchical data model that tends to consume an excessive amount of computing resources and slows down performance speed. In addition, its non-hierarchical data model also increases the difficulty of designing modern complex integrated circuits.
Although conventional grid-based routers and shape-based routers have been adequate to serve the routing process for IC designs, new IC routing technology is required because semiconductor fabrication process advancements are antiquating current technologies. Moreover, customers are continually demanding lower manufacturing costs, higher speed, more capacity, more capability, and increased performance from their routers.
Routers perform congestion and maximum flow analysis to determine the maximum number of routes or wires permitted in a given region of a chip layout. However, known congestion and maximum flow techniques are subject to significant drawbacks. For example, one approach for making a maximum flow analysis is to tessellate a design into grids, and determine the amount of wires that can be routed through the grid by forming tracts across the grid (either horizontal or vertical tracks depending upon the preferred routing direction). The number of tracts that span from one edge of the region or window to another without striking an object within the grid is used to determine the routing capacity of the grid. However, if a grid has a non-linear path that is free of obstructions, the free path is undetected by these methods.